﻿// Copyright (c) 2014 Morten Bakkedal
// This code is published under the MIT License.

using System;
using System.Collections.Generic;

namespace FuncLib.DualFunctions.Collections
{
	public class QuotientSet<T> where T : IEquatable<T>
	{
		private Dictionary<int, InnerQuotientSet> quotientSets;

		private QuotientSet()
		{
			quotientSets = new Dictionary<int, InnerQuotientSet>();
		}

		public static T[][] Compute(params T[] items)
		{
			QuotientSet<T> quotientSet = new QuotientSet<T>();
			foreach (T item in items)
			{
				quotientSet.Add(item);
			}

			return quotientSet.GetPartition();
		}

		private void Add(T item)
		{
			int hashCode = item.GetHashCode();
			
			InnerQuotientSet quotientSet;
			if (!quotientSets.TryGetValue(hashCode, out quotientSet))
			{
				quotientSet = new InnerQuotientSet();
				quotientSets.Add(hashCode, quotientSet);
			}

			quotientSet.Add(item);
		}

		private T[][] GetPartition()
		{
			List<T[]> partition = new List<T[]>();
			foreach (InnerQuotientSet quotientSet in quotientSets.Values)
			{
				foreach (List<T> items in quotientSet.GetPartition())
				{
					partition.Add(items.ToArray());
				}
			}
			return partition.ToArray();
		}

		private class InnerQuotientSet
		{
			private List<List<T>> partition;

			public InnerQuotientSet()
			{
				partition = new List<List<T>>();
			}

			public void Add(T item)
			{
				foreach (List<T> items in partition)
				{
					if (items[0].Equals(item))
					{
						// Equal to the first item, so must be equal to all items (an equivalence class).
						items.Add(item);
						return;
					}
				}

				// Add a new equivalence class.
				partition.Add(new List<T>(new T[] { item }));
			}

			public List<List<T>> GetPartition()
			{
				return partition;
			}
		}
	}
}
